package com.链表2;

/**
 * 请判断一个链表是否为回文链表。
 *
 * 示例 1:
 *
 * 输入: 1->2
 * 输出: false
 */
public class 回文链表 {
    static class Solution {
        /**
         * 用快慢 指针 反转后半断链表。
         * @param head
         * @return
         */
        public boolean isPalindrome(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;
            while (fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode tmp = null;
            if(fast != null){
                tmp = this.reserve(slow.next);
            }
            else{
                tmp  = this.reserve(slow);
            }
          ListNode tmp2 = head;
            while (tmp != null){
                if(tmp.val != tmp2.val){
                    return false;
                }
                else{
                    tmp2 = tmp2.next;
                    tmp = tmp.next;
                }

            }
            return true;
        }

        public ListNode reserve(ListNode head){
            ListNode pre =  null;
            ListNode cur = head;
            while (cur != null){
                ListNode tmp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = tmp;
            }
            return pre;
        }

    }



    public static void main(String[] args) {
        MyLinkedList link = new MyLinkedList(new int[]{1,1,2,1});
       // MyLinkedList link2 = new MyLinkedList();
        Solution solution = new Solution();
        boolean falg = solution.isPalindrome(link.head.next);
//        ListNode head = link.head;
//        ListNode tmp = new ListNode(-1);
//        tmp.next = head;
//        ListNode tmp2 = tmp;
//        tmp2.next.next = link2.head;

    }
}

